package pers.tz.题目.leetcode.树;

import pers.tz.common.TreeNode;
import pers.tz.common.TreeUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author irony
 * @date 2024-03-13
 */
public class leetcode_0144_二叉树的前序遍历 {
//给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
// 输入：root = [1,null,2,3]
//输出：[1,2,3]

    public static void main(String[] args) {
        TreeNode treeNode = TreeUtils.generateRandomTree();
        TreeUtils.preorderPrint(treeNode);

        System.out.println();
        List<Integer> integers = preorderTraversal(treeNode);
        System.out.println(integers);
    }

    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        traversal(ans, root);

        return ans;
    }

    private static void traversal(List<Integer> ans, TreeNode root) {
        if (root == null) {
            return;
        }

        ans.add(root.val);
        traversal(ans, root.left);
        traversal(ans, root.right);
    }


    // 迭代的方式实现
    public static List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> ans = new ArrayList<>();

        if (root == null) {
            return ans;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode head = stack.pop();
            ans.add(head.val);

            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }

        return ans;
    }
}
